#ifndef LRUCACHE_H
#define LRUCACHE_H

#include "../cachePolicy.h"
#include <cmath>
#include <cstddef>
#include <memory>
#include <mutex>
#include <thread>
#include <unordered_map>
#include <vector>

using namespace std;

namespace Cache {
template <typename Key, typename Value> class LRUCache;

template <typename Key, typename Value> class LRUNode {
private:
    Key key_;
    Value value_;
    size_t accCount_; // 访问次数
    shared_ptr<LRUNode<Key, Value>> prev_;
    shared_ptr<LRUNode<Key, Value>> next_;

public:
    LRUNode(Key k, Value v) : key_(k), value_(v), accCount_(1), prev_(nullptr), next_(nullptr) {
        // cout << "Successful LRUNode construct" << endl;
    }

    // 访问器
    Key getKey() const {
        return key_;
    }

    Value getValue() const {
        return value_;
    }

    void setValue(const Value &v) {
        value_ = v;
    }

    size_t getAccCount() const {
        return accCount_;
    }

    void increaceAccCount() {
        accCount_++;
    }

    friend class LRUCache<Key, Value>;
};

template <typename Key, typename Value> class LRUCache : public cachePolicy<Key, Value> {
public:
    using LRUNodeType = LRUNode<Key, Value>;
    using NodePtr = shared_ptr<LRUNodeType>;
    using NodeMap = unordered_map<Key, NodePtr>;

    LRUCache(size_t capacity) : capacity_(capacity) {
        initializeList();
        // cout << "Successful LRUCache construct" << endl;
    }

    ~LRUCache() override = default;

    void put(Key k, Value v) override {
        if (capacity_ <= 0)
            return;

        lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(k);
        if (it != nodeMap_.end()) {
            updateExistingNode(it->second, v);
            return;
        }
        addNewNode(k, v);
    }

    bool get(Key k, Value &v) override {
        auto it = nodeMap_.find(k);
        if (it != nodeMap_.end()) {
            moveToMostRecent(it->second);
            v = it->second->getValue();
            return true;
        }
        return false;
    }

    Value get(Key k) override {
        Value value{};
        get(k, value);
        return value;
    }

    void remove(Key k) {
        lock_guard<mutex> lock(mutex_);
        auto it = nodeMap_.find(k);
        if (it != nodeMap_.end()) {
            removeNode(it->second);
            nodeMap_.erase(k);
        }
    }

private:
    void initializeList() {
        // 创建首尾虚拟节点
        dummyHead_ = make_shared<LRUNodeType>(Key(), Value());
        dummyTail_ = make_shared<LRUNodeType>(Key(), Value());
        dummyHead_->next_ = dummyTail_;
        dummyTail_->prev_ = dummyHead_;
    }

    void updateExistingNode(NodePtr n, const Value &v) {
        n->setValue(v);
        moveToMostRecent(n);
    }

    void addNewNode(const Key &k, const Value &v) {
        if (nodeMap_.size() >= capacity_) {
            evictLeastRecent();
        }
        NodePtr newNode = make_shared<LRUNodeType>(k, v);
        insertNode(newNode);
        nodeMap_[k] = newNode;
    }

    void moveToMostRecent(NodePtr n) {
        removeNode(n);
        insertNode(n);
    }

    void removeNode(NodePtr n) {
        n->prev_->next_ = n->next_;
        n->next_->prev_ = n->prev_;
    }

    // 从尾部插入节点
    void insertNode(NodePtr n) {
        n->prev_ = dummyTail_->prev_;
        n->next_ = dummyTail_;
        dummyTail_->prev_->next_ = n;
        dummyTail_->prev_ = n;
    }

    void evictLeastRecent() {
        NodePtr leastRecent = dummyHead_->next_;
        removeNode(leastRecent);
        nodeMap_.erase(leastRecent->getKey());
    }

private:
    size_t capacity_; // 缓存容量
    NodeMap nodeMap_; // key -> Node
    mutex mutex_;
    NodePtr dummyHead_; // 虚拟头节点
    NodePtr dummyTail_; // 虚拟尾节点
};

// LRU-k
template <typename Key, typename Value> class LRUKCache : public LRUCache<Key, Value> {
public:
    LRUKCache(size_t capacity, int historyCapacity, int k)
        : LRUCache<Key, Value>(capacity), historyList_(make_unique<LRUCache<Key, size_t>>(historyCapacity)), k_(k) {
        // cout << "Successful LRUKCache construct" << endl;
    }

    Value get(Key k) override {
        // 获取访问次数
        int historyCount = historyList_->get(k);
        // 访问到数据则更新历史访问记录节点值++
        historyList_->put(k, ++historyCount);

        // 从缓存中获取数据
        // 不一定能获取到
        // 这里直接使用了基类的get方法，下同
        // 基类中已经实现了一条队列，派生类中可以直接使用基类中定义的接口
        return LRUCache<Key, Value>::get(k);
    }

    void put(Key k, Value v) override {
        // 检查是否已在缓存
        if (LRUCache<Key, Value>::get(k) != Value{}) {
            LRUCache<Key, Value>::put(k, v);
            return;
        }

        // 更新历史访问次数
        int historyCount = historyList_->get(k);
        historyList_->put(k, ++historyCount);

        if (historyCount >= k_) {
            historyList_->remove(k);
            LRUCache<Key, Value>::put(k, v);
        }
    }

private:
    int k_;
    unique_ptr<LRUCache<Key, size_t>> historyList_; // 访问历史数据
};

// 前两种lru只有一个区域，锁粒度大
template <typename Key, typename Value> class hashLRUCache : public cachePolicy<Key, Value> {
public:
    hashLRUCache(size_t capacity, size_t sliceNum)
        : capacity_(capacity), sliceNum_(sliceNum > 0 ? sliceNum : thread::hardware_concurrency()) {
        size_t sliceSize = (capacity + sliceNum_ - 1) / sliceNum_;
        for (int i = 0; i < sliceNum_; i++) {
            lruSliceCaches_.emplace_back(make_unique<LRUCache<Key, Value>>(sliceSize));
        }

        // cout << "Successful hashLRUCache construct" << endl;
    }

    void put(Key k, Value v) override {
        size_t sliceIdx = Hash(k) % sliceNum_;
        lruSliceCaches_[sliceIdx]->put(k, v);
    }

    bool get(Key k, Value &v) override {
        size_t sliceIdx = Hash(k) % sliceNum_;
        return lruSliceCaches_[sliceIdx]->get(k, v);
    }

    Value get(Key k) override {
        Value value{};
        get(k, value);
        return value;
    }

private:
    size_t Hash(Key k) {
        return hash<Key>{}(k);
    }

private:
    size_t capacity_;                                         // 总容量
    int sliceNum_;                                            // LRU切片数目
    vector<unique_ptr<LRUCache<Key, Value>>> lruSliceCaches_; // 若干切片LRU缓存
};
} // namespace Cache

#endif
